#include<bits/stdc++.h>
using namespace std;
const int PRE = 5e6+10;
#define int long long
int m;
int minP[PRE];
long long mu[PRE];
long long phi[PRE];
void init(){
    vector<int> p;
    phi[1] = 1;
    mu[1] = 1;
    for(int i = 2;i <= m;i++){
        if(!minP[i]){
            p.push_back(i);
            minP[i] = i;
            phi[i] = i - 1;
            mu[i] = -1;
        }
        for(int j = 0;1ll*i * p[j] <= m && minP[i] != p[j];j++){
            phi[i*p[j]] = phi[i] * phi[p[j]];
            mu[i * p[j]] = -mu[i];
            minP[i*p[j]] = p[j];
        }
        if(1ll*i*minP[i] <= m){
            phi[i*minP[i]] = phi[i]*minP[i];
            minP[i*minP[i]] = minP[i];
        }
    }
    for(int i = 1;i<=m;i++){
        phi[i] += phi[i - 1];
        mu[i] += mu[i - 1];
    }
}
unordered_map<int,int> mmp;
int query_sum_mu(int p){
    if(p <= m){
        return mu[p];
    }
    if(mmp.count(p)){
        return mmp[p];
    }
    int r = 0,res = 1;
    for(int l = 2;l <= p;l = r + 1){
        r = min(p/(p/l),p);
        res = res - (r - l + 1)*query_sum_mu(p/l);
    }
    mmp[p] = res;
    return res;
}
unordered_map<int,long long> pmp;
long long query_sum_phi(int p){
    if(p <= m){
        return phi[p];
    }
    if(pmp.count(p)){
        return pmp[p];
    }
    int r = 0;
    long long res = 1ll*p*(p + 1)/2;
    for(int l = 2;l <= p && l > 0;l = r + 1){
        r = min(p/(p/l),p);
        res = res - 1ll*(r - l + 1)*query_sum_phi(p/l);
    }
    pmp[p] = res;
    return res;
}
vector<int> qn;
signed main(){
    int T;
    cin>>T;
    int n = 0;
    for(int i = 1;i<=T;i++){
        int x;
        cin>>x;
        qn.push_back(x);
        n = max(n,x);
    }
    m = pow(4*n*T,2.0/3);
    init();
    for(int i =1;i<=T;i++){
        cout<<query_sum_phi(qn[i - 1])<<' '<<query_sum_mu(qn[i - 1])<<'\n';
    }
}